﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
using namespace std;
//list容器底层也是类模板，使用的数据结构是链表（双向带头循环）
//其大部分函数使用方式与vector类似（但list的迭代器类型是双向迭代器而非vector的随机迭代器）
//注：在STL中，​​所有标准容器（如 vector、list、map、set 等）均支持嵌套其他容器​​

//list的基础构造函数有四个，分别是默认构造，带参构造（空间，元素），
//带参构造（迭代器区间），拷贝构造
template<class T>
void print(const T& s)
{
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

//list::list
void test1()
{
	//默认构造
	list<int> lt1;
	//cout << lt1 << " ";->list同样不支持<<运算符重载，需手动实现打印函数
	print(lt1);//\n

	//带参构造（空间，元素）
	list<int> lt2(1);
	print(lt2);//0\n

	list<int> lt2s(3, 9);
	print(lt2s);//9 9 9\n

	//带参构造（迭代器区间）
	vector<int> v(5, 8);
	list<int> lt3(v.begin(), v.end());
	print(lt3);//8 8 8 8 8\n

	//拷贝构造
	list<int> lt4 = lt2;
	print(lt4);//9 9 9\n

	//list也能储存其他容器->在STL中，​​所有标准容器（如 vector、list、map、set 等）均支持嵌套其他容器​​
	list<vector<int>> ltvi;
}

//Capacity​​（当前已分配的、可用于存储元素的连续内存空间大小）:
//注：由于list底层为链表，所以不需要预先分配空间，也就没有reserve函数（但有resize）
void test2()
{
	//size()->返回当前list的size
	list<int> lt1(3, 999);
	cout << lt1.size() << endl;//3\n
	
	//empty()->判空
	list<int> lt2;
	if (lt2.empty())
	{
		cout << "空！" << endl;// 空！\n

	}
	else {
		cout << lt2.size() << endl;
	}
	lt2 = lt1;
	if (lt2.empty())
	{
		cout << "空！" << endl;
	}
	else {
		cout << lt2.size() << endl;//3\n
	}

	//max_size()->返回理论size最大值（一般实际值比理论值小不少）
	cout << lt1.max_size() << endl;//768614336404564650\n
	cout << lt2.max_size() << endl;//768614336404564650\n
}

//Element access（元素访问）:
void test3()
{
	list<int> lt(10, 0);
	//lt[0];//由于链表靠下标访问某个元素会有较大消耗，list并没有支持[]运算符重载
	//for (list<int>::iterator it = lt.begin(), int i = 0; it != lt.end(); ++it, ++i)//for中不能同时声明不同类型的变量
	int i = 0;
	for (list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
	{
		*it += i++;//->将lt中元素赋值为0~9，以便观察front和back
	}
	print(lt);//0 1 2 3 4 5 6 7 8 9\n

	//front
	cout << lt.front() << endl;//0\n

	//back
	cout << lt.back() << endl;//9\n
}

//Modifiers（更改元素值）:
void test4()
{
	//assign：替换容器中元素（容量不够时扩容，够时不释放多余空间，但list底层是链表，多余内存会被释放）
	//两个函数重载：迭代器区间版本和空间数量+元素版本（与构造函数类似）
	//​​注​​：assign 是​​全量替换​​，会清空容器并重新填充新内容。
	list<int> lt1(10, 0);
	cout << lt1.size() << endl;//10\n
	list<int> lt2(8, 1);
	vector<int> v(12, 3);
	//迭代器区间
	lt1.assign(lt2.begin(), lt2.end());
	cout << lt1.size() << endl;//8\n->可以发现，对于链表，会进行缩容
	print(lt1);//1 1 1 1 1 1 1 1\n
	lt1.assign(v.begin(), v.end());
	cout << lt1.size() << endl;//12\n
	print(lt1);//3 3 3 3 3 3 3 3 3 3 3 3\n
	//空间数量+元素
	lt1.assign(6, 4);
	cout << lt1.size() << endl;//6\n
	print(lt1);//4 4 4 4 4 4\n
	
	//注：emplace系列函数（C++11）与push功能相同，但效率稍高（直接新建容器，而非push的拷贝）
	
	//pop_front pop_back push_front push_back
	list<int> lt3;
	lt3.push_front(0);
	print(lt3);//0\n
	lt3.push_front(1);
	print(lt3);//1 0\n
	lt3.push_front(2);
	print(lt3);//2 1 0\n
	lt3.push_back(3);
	print(lt3);//2 1 0 3\n
	lt3.push_back(4);
	print(lt3);//2 1 0 3 4\n
	lt3.push_back(5);
	print(lt3);//2 1 0 3 4 5\n
	lt3.pop_back();
	print(lt3);//2 1 0 3 4\n
	lt3.pop_front();
	print(lt3);//1 0 3 4\n

	//insert erase：参数只能传迭代器
	list<int> lt4(1, 0);
	vector<int> v2(3, 3);
	print(lt4);//0\n
	lt4.insert(lt4.begin(), 99);
	print(lt4);//99 0\n
	lt4.insert(++lt4.begin(), 66);
	print(lt4);//99 66 0\n
	lt4.insert(++lt4.begin(), v2.begin(), v2.end());
	print(lt4);//99 3 3 3 66 0\n

	list<int>::iterator it = ++lt4.begin();//双向迭代器不支持+，这里只能采取++了
	while (it != lt4.end())
	{
		it = lt4.erase(it);//it接收erase的返回值用作下一次删除
	}
	print(lt4);//99\n

	//list自己的swap仍是交换指针，用以降低消耗
	list<int> lt5(3, 9);
	list<int> lt6(7, 10);
	cout << "lt5: ";
	print(lt5);//lt5: 9 9 9\n
	cout << "lt6: ";
	print(lt6);//lt6: 10 10 10 10 10 10 10\n
	lt5.swap(lt6);
	cout << "lt5: ";
	print(lt5);//lt5: 10 10 10 10 10 10 10\n
	cout << "lt6: ";
	print(lt6);//lt6: 9 9 9\n

	//resize：参数小于源数据则释放空间，大于则将额外开出的空间赋为初始值
	cout << "\nresize: " << endl;
	list<int> lt7(10, 1);
	cout << lt7.size() << endl;//10\n
	print(lt7);//1 1 1 1 1 1 1 1 1 1\n
	lt7.resize(3);
	cout << lt7.size() << endl;//3\n
	print(lt7);//1 1 1\n
	lt7.resize(18);
	cout << lt7.size() << endl;//18\n
	print(lt7);//1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n->多出的空间赋为初始值，这里是0

	//clear：清除容器内全部数据
	cout << "\nclear: " << endl;
	list<int> lt8(15, 999);
	cout << lt8.size() << endl;//15\n
	print(lt8);//999 999 999 999 999 999 999 999 999 999 999 999 999 999 999\n
	lt8.clear();
	cout << lt8.size() << endl;//0\n
	print(lt8);//\n
}

//Operations（操作）:
void test5()
{
	//元素操作函数：
	//splice
	//功能：将一个 list 中的元素转移到另一个 list 的pos之前（注意是转移，而非复制）
	//特点：高效操作，不需要元素拷贝，直接修改指针连接
	//注：以下函数迭代器并非模板，因此不能传其他容器的迭代器
	//void splice (iterator position, list& x);//移动整体
	//void splice (iterator position, list& x, iterator i);//移动单个元素，i指的是x中的某个特定元素
	//void splice (iterator position, list& x, iterator first, iterator last);//移动区间
	list<int> lt1(6, 1);
	list<int> lt2(10, 0);
	int i = 0;
	for (list<int>::iterator it = lt2.begin(); it != lt2.end(); ++it)
	{
		*it += i++;//->将lt中元素赋值为0~9，以便观察front和back
	}
	print(lt2);//0 1 2 3 4 5 6 7 8 9\n
	list<int> lt1_cpy = lt1;
	list<int> lt2_cpy = lt2;
	lt1_cpy.splice(lt1_cpy.begin(), lt2_cpy);
	print(lt1_cpy);//0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1\n
	print(lt2_cpy);//\n

	lt1_cpy = lt1;
	lt2_cpy = lt2;
	lt1_cpy.splice(lt1_cpy.begin(), lt2_cpy, lt2_cpy.begin());
	print(lt1_cpy);//0 1 1 1 1 1 1\n
	print(lt2_cpy);//1 2 3 4 5 6 7 8 9\n

	lt1_cpy = lt1;
	lt2_cpy = lt2;
	lt1_cpy.splice(lt1_cpy.begin(), lt2_cpy, ++lt2_cpy.begin(), --lt2_cpy.end());
	print(lt1_cpy);//1 2 3 4 5 6 7 8 1 1 1 1 1 1\n
	print(lt2_cpy);//0 9\n

	//remove：删除所有==参数的元素
	lt1_cpy.remove(1);
	print(lt1_cpy);//2 3 4 5 6 7 8

	//remove_if
	//功能：删除满足特定条件的元素
	//需要提供一个谓词函数（返回bool的可调用对象）
	//示例：list.remove_if([](int x) {return x % 2 == 0; }) 删除所有偶数
	/*bool func(int x)
	{
		return x % 2 == 0;
	}*/
	lt1_cpy.remove_if([](int x) {return x % 2 == 0; });
	print(lt1_cpy);//3 5 7\n

	//unique
	//功能：删除连续的重复元素（通常需要先排序）
	list<int> lt3(10, 0);
	int j = 0;
	for (list<int>::iterator it = ++lt3.begin(); it != --lt3.end(); ++it)
	{
		*it += j++;
	}
	*(--lt3.end()) = 0;
	print(lt3);//0 0 1 2 3 4 5 6 7 0\n
	lt3.unique();
	print(lt3);//0 1 2 3 4 5 6 7 0\n->默认是删除的是连续且相同的元素，因此首尾均剩下了一个0
}

int main()
{
	test1();
	//test2();
	//test3();
	//test4();
	//test5();
	return 0;
}